package com.demo.datastructure.heap;

/**
 * @description: 堆排序
 * @author: ljr
 * @time: 2021/6/22 16:37
 */
public class HeapDemo {

    private int[] nodes;

    private int n;  //堆的大小

    private int count; //已存在的数据

    public HeapDemo() { }

    public HeapDemo(int capacity){
        nodes = new int[capacity+1];
        n = capacity;
        count = 0;
    }

    public void insert(int data) {
        if(count >= n){ return; }
        count++;
        nodes[count] = data;
        int index1 = count;
        while(index1/2 > 0 && nodes[index1] > nodes[index1/2]){
            swap(nodes, index1, index1/2);
            index1 = index1/2;
        }
    }


    public void removeMax() {
        if(count == 0){return;}
        nodes[1] = nodes[count];
        --count;
        heapify(count,1);
    }

    private void heapify(int count, int i) {
        while(true){
           int maxPos = i;
           if(i*2 <= count && nodes[i] < nodes[i*2])  maxPos = i*2;
           if(i*2+1 <= count && nodes[maxPos] < nodes[i*2+1])  maxPos = i*2+1;
           if(maxPos == i) break;
           swap(nodes, i, maxPos);
           i = maxPos;
        }
    }


    public void sort(int[] a, int n){
        buildHeap(a, n);
        int k =  n;
        while (k > 1){
            swap(a, 1, k);
            --k;
            heapify(k,1);
        }
    }


    public void buildHeap(int[] a, int n){
        if(a == null || a.length == 0) return;
        nodes = a;
        for(int i = n/2; i >= 1; i--){
            heapify(n, i);
        }
    }


    private void swap(int[] nodes, int index1, int index2){
        int num = nodes[index2];
        nodes[index2] =  nodes[index1];
        nodes[index1] = num;
    }

}
